/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a binary tree, return the zigzag level order traversal of
 *              its nodes' values. (ie, from left to right, then right to left
 *              for the next level and alternate between).
 * 
 *              For example: Given binary tree {3,9,20,#,#,15,7}, 
 *              	3 
 *                 / \ 
 *                9   20 
 *                    / \
 *              	 15  7 
 *              
 *              return its zigzag level order traversal as: 
 *              [ 
 *              	[3], 
 *              	[20,9],
 *              	[15,7] 
 *              ]
 */
public class BinaryTreeZigzagLevelOrderTraversal {

	private class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (null == root)
			return res;
		
		List<Integer> list = new ArrayList<Integer>();
		Queue<TreeNode> curLevel = new LinkedList<TreeNode>();
		Stack<TreeNode> stack = new Stack<TreeNode>();
		boolean isPositive = false;
		curLevel.add(root);
		
		while (!curLevel.isEmpty()) {
			TreeNode cur = curLevel.poll();
			list.add(cur.val);
			
			if (!isPositive) {
				if (null != cur.left)
					stack.push(cur.left);
				if (null != cur.right)
					stack.push(cur.right);
			} else {
				if (null != cur.right)
					stack.push(cur.right);
				if (null != cur.left)
					stack.push(cur.left);
			}
			
			if (curLevel.isEmpty()) {
				res.add(list);
				list = new ArrayList<Integer>();
				while (!stack.isEmpty()) {
					curLevel.add(stack.pop());
				}
				stack.clear();
				isPositive = !isPositive;
			}
		}
		
		return res;
    }

	@Test
	public void test() {
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		
		List<List<Integer>> res = zigzagLevelOrder(n1);
		for (List<Integer> list : res) {
			for (int i : list) {
				System.out.print(i + ",");
			}
			System.out.println();
		}
	}
}
